每天固定念一種類型的題目，結果清單裡待寫但還沒寫的題目越來越多了QQ
接下來會念一陣子的 DP，估計要花上一到兩週的時間，最後再用圖論的東西來收尾。

今天要看的是 DP 背包問題中最基礎的 0-1 背包。

0-1 背包是在條件限制（有限容量）下去最大化收益（物品價值），基本做法就是開二維陣列，一個維度是容量，另一個維度是物品選取狀況，記錄「在可以選取前 i 項物品時，限重 j 能獲取的最大價值」。大概記得這點，然後寫出二維的轉移矩陣就完成了，hard 題可能需要開到三維，轉移矩陣的限制也會變多。

416. Partition Equal Subset Sum 這題其實不用寫 dp 矩陣，只需要 dp 的核心概念：記錄每個選擇和選擇的後果。每個物品可以選或不選，然後記載所有的可能性，判斷是否符合題目要求就好了。

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if sum(nums) % 2 == 1:
            return False
        target = sum(nums) / 2

        s = set()
        s.add(0)

        for i in nums:
            tmp = list(s)
            if target in tmp:
                return True
            for j in tmp:
                s.add(j+i)

        return target in tmp

• 參考資料
  • 【科学派 DP】一份「路径问题从入门到进阶」的究极指南
    • 原本打算先刷路徑問題接 DP，不過寫了前兩題沒想像中難，打算跟 DP 並行一起寫
  • 宮水三叶的刷题日记#背包问题
  • 最全 LeetCode 背包问题目录
    • 接下來幾天的背包問題大概會跟著這兩篇的架構走

• 路徑問題
  • 62. Unique Paths
  • 63. Unique Paths II
• 0-1背包問題
  • 416. Partition Equal Subset Sum

• Total Count: 10
  • 是今天剛好都挑到 easy 題嗎，寫 dp 居然比前幾天順手我完全沒想過 (ﾟдﾟ≡ﾟдﾟ)
  • 然後刷題小目標快沒救了(ﾒ ﾟ皿ﾟ)ﾒ